package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-14 10:45
 * @description: Functions of this class is
 * 官方题解：
 * class Solution {
 *     public int candy(int[] ratings) {
 *         int n = ratings.length;
 *         int ret = 1;
 *         int inc = 1, dec = 0, pre = 1;
 *         for (int i = 1; i < n; i++) {
 *             if (ratings[i] >= ratings[i - 1]) {
 *                 dec = 0;
 *                 pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
 *                 ret += pre;
 *                 inc = pre;
 *             } else {
 *                 dec++;
 *                 if (dec == inc) {
 *                     dec++;
 *                 }
 *                 ret += dec;
 *                 pre = 1;
 *             }
 *         }
 *         return ret;
 *     }
 * }
 **/
public class NoNo分发糖果 {
    public static void main(String args[]){
        System.out.println(candy(new int[]{1,2,2}));
    }

    /**
     * 分糖果问题题目描述：
     * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
     * 我需要按照以下要求，帮助老师给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
     * 那么这样下来，老师至少需要准备多少颗糖果呢？
     *
     *
     * 样例：
     * 输入：[1,2,2]
     * 输出：4
     *
     * 解释：按照贪心思想，老师至少需要分别给这三个孩子分发 1、2、1 颗糖果。
     *
     */
    public static int candy(int[] ratings) {
        int len=ratings.length;
        int ans=0;//初始化总糖果数为0
        int candys[]=new int[len];//先声明一个数组存每个人得到的糖果总数
        candys[0]=candys[len-1]=1;//然后初始化第一个孩子和最后一个孩子有一个糖果

        for(int i=1;i<len;i++){//从第一个人向右开始遍历
            if(ratings[i]>ratings[i-1]&&candys[i]<=candys[i-1]){//如果左边那个孩子的排名比当前孩子的低，但是左边那个孩子糖果数大于等于当前人的话
                //则当前孩子糖果数=左边那个人的糖果数+1
                candys[i]=candys[i-1]+1;
            }
            else{
                //否则当前这个人的糖果数就为1个
                candys[i]=1;
            }
        }
        //因为题目要求排名较高的孩子的糖果数要比左右的孩子的都要高，所以还要进行向左的循环
        for(int i=len-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]&&candys[i]<=candys[i+1]){//同理，如果右边那个孩子的排名比当前孩子的低，但是右边那个孩子糖果数大于等于当前人的话
                //则当前孩子糖果数=右边那个人的糖果数+1
                candys[i]=candys[i+1]+1;
            }
        }

        //最后把每个孩子的糖果数加到一起就是答案
        for(int candy:candys){
            ans+=candy;
        }

        return ans;//然后将答案返回
    }
}